from collections import defaultdict


class Solution:
    def palindromePairs(self, words: list) -> list:
        mid_dict = defaultdict(int)
        res = set()
        for index, word in enumerate(words):
            mid_dict[word] = index
        for index, word in enumerate(words):
            length = len(word)
            if word[::-1] in mid_dict:
                res.add((mid_dict[word[::-1]], index))
            for i in range(1, length):
                if word[:i] == word[i-1::-1] and word[:i-1:-1] in mid_dict:
                    res.add((mid_dict[word[:i - 1:-1]], index))
            for i in range(1, length):
                if word[-i:] == word[:-i-1:-1] and word[-i-1::-1] in mid_dict:
                    res.add((index, mid_dict[word[-i-1::-1]]))
            if word and word == word[::-1] and "" in mid_dict:
                res.add((mid_dict[""], index))
                res.add((index, mid_dict[""]))
        return [list(i) for i in res if i[0] != i[1]]


a = Solution()
print(a.palindromePairs(["abcd", "dcba", "lls", "s", "sssll"]))
print(a.palindromePairs(["bat", "tab", "cat"]))
print(a.palindromePairs(["a", ""]))
print(a.palindromePairs(["abc", "cba"]))
print(a.palindromePairs(["a", "abc", "aba", ""]))
print(a.palindromePairs(["a", "aa", "aaa"]))
print(a.palindromePairs(["bb","bababab","baab","abaabaa","aaba","","bbaa","aba","baa","b"]))
